public class _42接雨水 {
    /**
     * 动态规划
     * @param height
     * @return
     */
    public static int trap(int[] height) {
        int length = height.length;
        int[] leftMax =new int[length];
        leftMax[0] =height[0];
        for (int i = 1; i < length; i++) {
            leftMax[i] = Math.max(height[i], leftMax[i-1]);
        }

        int[] rightMax =new int[length];
        rightMax[length-1] =height[length-1];
        for (int i = length-2; i >=0; i--) {
            rightMax[i] = Math.max(height[i], rightMax[i+1]);
        }
        int r=0;
        for (int i = 0; i < length; i++) {
            r += Math.min(leftMax[i], rightMax[i])-height[i];
        }
        return r;
    }

    public static void main(String[] args) {
        // int[] a={0,1,0,2,1,0,1,3,2,1,2,1};
        int[] a={4,2,0,3,2,5};
        int trap = trap(a);
        System.out.println("42result:"+trap);
    }
}
